package sort;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;


/**
 * @Author Zhouchb
 * @Create 2021-10-2021/10/26 :20:13
 * @Description
 */
public class MergerSort {
    public static Comparable arrSort[];

    public static void main(String[] args) throws Exception {
        Integer[] i = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        arrSort = new Comparable[i.length];
        long start = System.currentTimeMillis();
        System.out.println(start);
        sort(i, 0, i.length - 1);
        long end = System.currentTimeMillis();
        System.out.println(end);
        System.out.println(Arrays.toString(i));
        System.out.println(Arrays.toString(arrSort));

        System.out.println(end - start);
    }

    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    private static void sort(Integer[] i, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (r + l) / 2;
        sort(i, l, mid);
        sort(i, mid + 1, r);
        merger(i, l, mid, r);

    }

    public static void merger(Comparable[] arr, int l, int mid, int r) {
        int i = l;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            if (compare(arr[p1], arr[p2])) {
                arrSort[i++] = arr[p2++];
            } else {
                arrSort[i++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
            arrSort[i++] = arr[p1++];
        }
        while (p2 <= r) {
            arrSort[i++] = arr[p2++];
        }
        for (int x = l; x <= r; x++) {
            arr[x] = arrSort[x];
        }
    }
  /*  public static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }


    public static boolean compare(Comparable a, Comparable b) {
        return a.compareTo(b) > 0;
    }

    public static void merge(Comparable[] a, int l, int mid, int r) {
        int i = l;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            if (compare(a[p1], a[p2])) {
                arrSort[i++] = a[p2++];
            } else {
                arrSort[i++] = a[p1++];
            }
        }
        while (p1 <= mid) {
            arrSort[i++] = a[p1++];
        }
        while (p2<= r) {
            arrSort[i++] = a[p2++];
        }
       for (int x=l;x<=r;x++){
           a[x]=arrSort[x];
       }
    }*/

}

class haha {
    public static int tempArr[];

    public static void main(String[] args) {
        int[] i = {9, 6, 1, 3, 8, 7, 5};//{9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
        tempArr = new int[i.length];
        sort(i, 0, i.length - 1);
        System.out.println(Arrays.toString(tempArr));
    }

    public static void sort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (r + l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        System.out.println("我只会执行一次");
        merge(arr, l, mid, r);
    }

    public static void merge(int[] arr, int l, int mid, int r) {
        int i = l;
        int p1 = l;
        int p2 = mid + 1;
        while (p1 <= mid && p2 <= r) {
            if (arr[p1] < arr[p2]) {
                tempArr[i++] = arr[p1++];
            } else {
                tempArr[i++] = arr[p2++];
            }

        }
        while (p1 <= mid) {
            tempArr[i++] = arr[p1++];
        }
        while (p2 <= r) {
            tempArr[i++] = arr[p2++];
        }
        for (int k = l; k <= r; k++) {
            arr[k] = tempArr[k];
        }
    }
}
